class Solution {
public:
    vector<vector<string>> ret;
    bool check[10] = {false};
    bool checkQ(vector<string>& path, int n, int max) {
        int i = path.size() - 1;
        for (int i = path.size() - 1; i >= 0; i--) {
            int op = path.size() - i;
            if (n - op >= 0 && path[i][n - op] == 'Q')
                return true;
            else if (n + op < max && path[i][n + op] == 'Q')
                return true;
        }
        return false;
    }
    void dfs(int n, vector<string> path) {
        if (path.size() == n) {
            ret.push_back(path);
            return;
        }
        for (int i = 0; i < n; i++) {
            if (check[i] == false) {
                if (path.size() > 0 && checkQ(path, i, n))
                    continue;
                string s(n, '.');
                s[i] = 'Q';
                check[i] = true;
                path.push_back(s);
                dfs(n, path);
                check[i] = false;
                path.pop_back();
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        dfs(n, vector<string>());
        return ret;
    }
};